'''
https://leetcode.cn/problems/word-break/description
'''
from typing import List
from functools import cache

class Node:
    def __init__(self):
        self.ended = False
        self.next = {}
class Solution:

    def insert(self, word):
        cur = self.root
        for c in word:
            if c not in cur.next:
                cur.next[c] = Node()
            cur = cur.next[c]
        cur.ended = True

    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        self.root = Node()
        for word in wordDict:
            self.insert(word)
        n = len(s)
        @cache
        def f(i):
            if i == n: return True
            l = i
            cur = self.root
            for r in range(l, n):
                if s[r] not in cur.next:
                    break
                cur = cur.next[s[r]]
                if cur.ended and f(r+1):
                    return True
            return False
        return f(0)

    def wordBreak2(self, s: str, wordDict: List[str]) -> bool:
        self.root = Node()
        for word in wordDict:
            self.insert(word)
        n = len(s)
        dp = [False] * n + [True]
        for i in range(n-1, -1, -1):
            l = i
            cur = self.root
            for r in range(l, n):
                if s[r] not in cur.next:
                    break
                cur = cur.next[s[r]]
                if cur.ended and dp[r+1]:
                    dp[i] = True
                    break
        return dp[0]




s = 'catsandog'
wordDict = ["cats","dog","sand","and","cat"]
print(Solution().wordBreak(s, wordDict))


